#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool dfs(int k, int i, int j, vector<vector<char>>& board, string word, vector<vector<bool>> &vis){
        if(vis[i][j]) return false;
        else vis[i][j] = true;
        if(word[k]!=board[i][j]) {vis[i][j] = false;return false;}
        if(k == word.size()-1) return word[k] == board[i][j];
        if(i>0 && dfs(k+1, i-1, j, board, word, vis) == true) {vis[i][j] = false;return true;}
        if(j>0 && dfs(k+1, i, j-1, board, word, vis) == true) {vis[i][j] = false;return true;}
        if(i<board.size()-1 && dfs(k+1, i+1, j, board, word, vis) == true) {vis[i][j] = false;return true;}
        if(j<board[0].size()-1 && dfs(k+1, i, j+1, board, word, vis) == true) {vis[i][j] = false;return true;}
        vis[i][j] = false;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        vector<pair<int,int>> vec;
        int m=board.size(); int n=board[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(dfs(0, i, j, board, word, vis)==true) return true;
            }
        }
        return false;
    }
};

int main(){
    Solution solution;
    vector<vector<char>> board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    string word = "ABCCED";
    solution.exist(board, word);
}